package 动态规划;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个数组，不能取两个下标相邻的元素，求能取出的最大值
 * 例如{1,3,5,7,5};要么取1，5，5 要么取3,7
 *
 * 2的问题:
 *  2是用递归完成，递归可能存在栈溢出的风险，而且递归相对于迭代性能较差
 *
 * 例1和例2(递归)的思想：
 *  f(n)都是从后f(n-1)往前f(0)递归，再根据f(0)的值往后得出f(n-1)的值。即 先从后面 把问题推给前面的 再通过前面的答案 得出自己的答案
 * 迭代的思路：
 *  既然f(0)我们是已知的，那么f(1)也可以通过比较 f(0)与nums[1] 来得出答案
 *  f(2)也可以通过比较 f(1)和f(0)+nums[2] 来得出答案
 *  那么可以这种方式直到推到 f(n)为止
 */
public class Ch03_打家劫舍迭代 {
    public static void main(String[] args) {
//        System.out.println("83".hashCode());
        int[] nums={1,3,5,7,5,72,1,4,7};
        System.out.println(maxMoney(nums));
    }

    public static int maxMoney(int[] nums){
        if (nums==null||nums.length==0){
            return 0;
        }
        if (nums.length<2){
            return nums[0];
        }
        int[] dp=new int[3];
        //dp[0]表示待求结果的上 上 一个
        dp[0]=nums[0];

        dp[1]=Math.max(dp[0],nums[1]);

        for (int i=2;i<nums.length;i++){
//          dp[2]是待求结果的那个
            dp[2]=Math.max(dp[1],dp[0]+nums[i]);    //f(n)
            dp[0]=dp[1];    //dp[0]是待求结果的 上 上 一个。这一步是将 上一个结果移到 上 上 一个 结果
            dp[1]=dp[2];    //dp[1]是带求结果的 上一个。  这一步是将当前结果移到 上一个结果
        }
        return dp[1];   //返回dp[1]因为 我们最后会将结果移入到dp[1]
    }
}
